/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package com.sx.sx1.lintcode.day717;

import java.util.*;

/**
 *
 * @author Administrator
 */
public class LC1101 {

    static class TreeNode {

        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    static class Solution {

        /**
         * @param root: the root
         * @return: the maximum width of the given tree
         */
        public int widthOfBinaryTree(TreeNode root) {
            //BFS
            if (root == null) {
                return 0;
            }
            List<TreeNode> q1 = new ArrayList<>(); //队列1,BFS，普通题用Queue,这里用list模拟
            List<Integer> q2 = new ArrayList<>(); //队列2,BFS，普通题用Queue,这里用list模拟

            q1.add(root);
            q2.add(0);

            int ans = 1;
            while (!q1.isEmpty()) {
                int size = q1.size();
                int curlen = 1;
                if (size > 1) {
                    int start = q2.get(0);
                    int end = q2.get(size - 1);
                    curlen = end - start + 1;
                }

                if (ans < curlen) {
                    ans = curlen;
                }

                List<TreeNode> q1bak = new ArrayList<>();
                List<Integer> q2bak = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    TreeNode pop = q1.get(i);
                    int idx = q2.get(i);

                    if (pop.left != null) {
                        q1bak.add(pop.left);
                        q2bak.add(2 * idx + 1);
                    }

                    if (pop.right != null) {
                        q1bak.add(pop.right);
                        q2bak.add(2 * idx + 2);
                    }
                }

                q1 = q1bak;
                q2 = q2bak;
            }

            return ans;
        }
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        t1.left = new TreeNode(3);
        t1.right = new TreeNode(2);
        t1.left.left = new TreeNode(5);
        t1.right.right = new TreeNode(9);
        t1.left.left.left = new TreeNode(6);
        t1.right.right.right = new TreeNode(7);

        Solution obj = new Solution();
        System.out.println(obj.widthOfBinaryTree(t1));
    }
}


/*LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有166条未读消息，请及时查看
1101 · 二叉树最大宽度
算法
中等
通过率
50%

题目
题解18
笔记
讨论42
排名
记录
描述
给定一颗二叉树, 编写一个函数求该树的最大宽度, 即该树每一层的宽度的最大值. 该二叉树具有与满二叉树相同的结构, 但是一些节点为空 null.

二叉树某一层的宽度定义为该层两端节点之间的距离. 注意, 两端节点之间的空节点也算作长度.

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


答案值会在32位有符号整数的范围内.

样例
样例1:

输入: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

输出: 4
解释: 第三层的最大宽度为4：(5,3,#,9)。
样例2:

输入: 

          1
         /  
        3    
       / \       
      5   3     

输出: 2
解释: 最大长度在第三层，长度为2: (5,3)。
样例3:

输入: 

          1
         / \
        3   2 
       /        
      5      

输出: 2
解释: 最大长度在第二层，长度为2：(3,2).
样例4:

输入: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
		
输出: 8
解释: 最大长度在第四层，长度为8： (6,#,#,#,#,#,#,7).
标签
企业
Amazon
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
1/3307
已开启智能提示
发起考试
30 分 00 秒
123456789101112131415161718192021
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
…}
控制台
历史提交

 */
